A public data communications network such as the Internet is formed of a plurality of networks connected to each other, wherein each of the constituent networks maintains its identity. Each network supports communication among devices connected to the networks, and the networks in their turn are connected by routers. Thus, the Internet can be considered to comprise a mass of routers interconnected by links. Data packets are transmitted over links from one router to the next one on their ways towards the final destinations. In each router a forwarding decision is performed on incoming packets to determine the packets next-hop router.
A data packet consists of a so-called “header” together with the piece of data. The header consists of a number of fields, where each field contains information including where the packet comes from and where it should be sent.
When the packets travel on the Internet they are sorted into different flows according to one or several fields in the headers. The header fields used to sort a packet into the right flow are referred to as the “input key”.
The routers use the input key to search for the corresponding flow that the packet belongs to. The search is done in a table called a “classifier”. The classifier consists of a list of so-called “rules”. Each rule consists of D fields and represents a flow. A packet matches a rule if the header fields in the input key matches the corresponding fields in the rule.
FIG. 1B illustrates a typical classifier with six rules with five fields each and each rule has a flow associated with it. The first field in the classifier is named the destination address (DA), the second field is named the source address (SA), the third field is named the destination port (DP), the fourth field is named the source port (SP) and the fifth field is named the protocol (PR). The first and the second fields are represented by prefixes, the third and fourth fields are represented by numbers and the fifth field is represented by a protocol number.
To summarize, specific data forwarding and/or processing actions depending on the nature of the data traffic, such as blocking data traffic, is provided by classification of incoming data, such as packet classification or multi-field classification. This is provided by a process of inspecting values of selected header fields of a data packet and selecting a first matching rule. The selection is provided by selecting (or finding) from a list of rules or classes the first rule that matches a packet. In principle, each rule consists of D intervals where D is the number of header fields in the packet (or the potential number of header fields of interest). A packet is said to match a rule when the value of each header field of the packet lies within the corresponding interval in the rule. That is, the values contained in all header fields of the packet must match their corresponding interval in the rule.
Thus, to be able to determine to which flow each packet belongs the header fields of the packets are inspected and compared to the list of rules that identify each flow.
This is in the following referred to the “packet classification problem”, which is a problem to be solved. The packet classification problem is to determine the first matching rule for each incoming packet at a router.
There are many algorithms solving the packet classification problem and these algorithms can typically be broken down into four types: exhaustive search, decision tree, decomposition and “Tuple space”.
Exhaustive Search
The two most common approaches in exhaustive search are linear search and parallel search. Linear search checks every rule in the classifier until a match is found. Parallel search divides the classifier into subsets containing one rule each and then the subsets are searched in parallel. The parallel search can be done using Ternary Content Addressable Memory (TCAM) where one processor is assigned to each rule.
Decision Tree
The classifier is analyzed in order to make a number of cuts and then a decision tree is constructed from the cuts. An input key is constructed from the header fields of the packet and the decision tree is traversed until a leaf is found.
Decomposition
The multiple field searches are decomposed into instances of single field searches. Independent searches on each packet field are made and the results are combined in the end.
Tuple Space
The classifier is partitioned according to the number of specified bits in the rules. This approach is based on the assumption that the intervals constituting the rules are represented by prefixes. The partitions or a subset of the partitions are probed using exact match searches.